import java.util.*;

//解法 ： 暴力回溯
//求解图着色的最少色料数
//给定图 求颜色

public class Solution_1 {
    Graph graph ;
    boolean[] flags ;
    int min_color = 1<<30 ;
    int version = 0 ;
    int[] ans ;
    int flagCnt = 0 ;
    int pointNub  ;
    public long begintime;

    void printNow_Best(){
        System.out.println("最优解一共用了_"+min_color+"_种颜色!!\n");
        for(int i=0;i<ans.length;i++){
            System.out.println("点_"+i+"_的颜色是_"+ans[i]+"_");
        }
        System.out.println("\n");
    }

    void printNowBestNub(){
        System.out.println(++version+" : 当前最优解一共用了： "+min_color+" 种颜色. "+getLateTime()+"ms\n");
    }

    void Choice(List<Integer> colorPoint,int cnt){
        if(cnt==colorPoint.size()-1){
            if(flagCnt+colorPoint.size()==pointNub){
                //说明整个图已经上色完成
                min_color = graph.colorNub ;
                ans = graph.nodeColor.clone();
                printNowBestNub();
            }else {
                //开始下一层dfs_for_ans
                if(min_color>graph.colorNub){
                    flagCnt += colorPoint.size() ;
                    dfs_for_ans(colorPoint);
                    flagCnt -= colorPoint.size() ;
                }
            }
        }else{
            //否则下一层颜色dfs_for_color
            dfs_for_color(colorPoint,cnt+1);
        }
    }

    //colorPoint:这个递归过程要上4色的所有点  cnt：现在已经上色到哪一个点
    void dfs_for_color(List<Integer> colorPoint,int cnt){
        //当前要涂的点的编号
        int point = colorPoint.get(cnt) ;
        //System.out.println(point);
        //标记当前的点
        flags[point] = true ;
        //获取这个点周围的颜色
        boolean[] usedColor =graph.getAroundColors(point) ;
        boolean flagHaveUsed = false ;

        for(int i=1;i< usedColor.length&&graph.colorNub<min_color;i++){
            //找到可以用的颜色填上
            if(!usedColor[i]){
                flagHaveUsed = true ;
                graph.nodeColor[point] = i ;
                //选择下一步发展的方向
                Choice(colorPoint,cnt);
                graph.nodeColor[point] = 0 ;
            }
        }

        //
        if(!flagHaveUsed&&graph.colorNub+1<min_color){
            //发现颜色不够用,拓展颜色范围
            graph.nodeColor[point] = usedColor.length ;
            graph.colorNub++ ;
            //选择下一步发展的方向
            Choice(colorPoint,cnt);
            //恢复现场
            graph.colorNub-- ;
            graph.nodeColor[point] = 0 ;
        }

        //解锁
        flags[point] = false ;
    }


    List<Integer> removeNubEqu(List<Integer> list){
        Set<Integer> set = new LinkedHashSet<>() ;
        set.addAll(list);
        list.clear();
        list.addAll(set) ;
        return list ;
    }

    void dfs_for_ans(List<Integer> father){
        //首先找到与上一个点集连接的所有点
        List<Integer> child = new ArrayList<>() ;
        for(int item : father){
            //遍历与这个点连接的所有边
            for(int i=graph.head[item];i!=-1;i=graph.edges[i].next){
                //如果这条边所指向的点没有被用过则加入
                int next = graph.edges[i].to ;
                if(!flags[next]){
                    child.add(next) ;
                }
            }
        }

        //除重
        removeNubEqu(child) ;
        //找完所有点之后准备给子点上色，上色前要提前算出所有的可能以便于回溯
        //上色的依据得根据 父节点群 与 兄弟节点群 的限制来上色
        //其中父节点群在每次上色都不会有改动 ， 但是对于兄弟节点群来说由于顺序的不同会使得后续上色的节点不同
        //因此这里要采用递归的方法 来给兄弟节点群来计算出上色的可能性

        //颜色状态的保存方法：将所有点的颜色状态保存在一个32位的int类型里面  每一个节点对应最多有4种颜色因此可以用两位代表一个节点的颜色状态
        //                 因此 32/2 = 16 最多可以同时保存16个节点的颜色 所以该算法的最大涂色节点数位 16

        //用于接收 兄弟群的所有涂色集
        if(child.size()==0){
            System.out.println("hahah");
        }

        List<Integer> colorStatus = new ArrayList<>();
        //为兄弟节点上色
        dfs_for_color(child,0) ;
    }

    long getLateTime(){
        return  (System.currentTimeMillis()-begintime) ;
    }

    void initSolution(int nodeNub ,int maxEdges ){
        begintime = System.currentTimeMillis() ;
        pointNub = nodeNub ;
        //整一个flag出来
        flags = new boolean[nodeNub];
        //存储最优解的数组
        ans = new int[nodeNub] ;
        //建一个链式前向星
        graph = new Graph(nodeNub,maxEdges,1) ;
        //提前标记第一个点的颜色
        graph.nodeColor[0] = 1  ;
        //已经使用
        flags[0] = true ;
        flagCnt = 1  ;
        List<Integer> father = new ArrayList<>() ;
        father.add(0) ;
        //开始深搜答案
        graph.printGraph();
        dfs_for_ans(father);
        System.out.println("end");
        printNow_Best();
    }

    public static void main(String[] args) {
        Solution_1 solution2 = new Solution_1() ;
        solution2.begintime = System.currentTimeMillis() ;
        solution2.initSolution(100,350);
        System.out.println("总用时："+solution2.getLateTime()+"mss");
    }
}
